<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>第十章－基本的数据结构 | 章军的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="第十章 — 基本的数据结构动态集合的元素">
<meta name="keywords" content="data struct">
<meta property="og:type" content="article">
<meta property="og:title" content="第十章－基本的数据结构">
<meta property="og:url" content="http://octopuscloud.top/2019/04/21/十章－数据结构/index.html">
<meta property="og:site_name" content="章军的博客">
<meta property="og:description" content="第十章 — 基本的数据结构动态集合的元素">
<meta property="og:locale" content="China">
<meta property="og:updated_time" content="2019-09-11T04:27:11.804Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="第十章－基本的数据结构">
<meta name="twitter:description" content="第十章 — 基本的数据结构动态集合的元素">
  
    <link rel="alternate" href="/atom.xml" title="章军的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">章军的博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://octopuscloud.top"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-十章－数据结构" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/04/21/十章－数据结构/" class="article-date">
  <time datetime="2019-04-21T05:15:37.000Z" itemprop="datePublished">2019-04-21</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      第十章－基本的数据结构
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="第十章-—-基本的数据结构"><a href="#第十章-—-基本的数据结构" class="headerlink" title="第十章 — 基本的数据结构"></a>第十章 — 基本的数据结构</h1><h2 id="动态集合的元素"><a href="#动态集合的元素" class="headerlink" title="动态集合的元素"></a>动态集合的元素</h2><a id="more"></a>
<pre><code>动态集合的对象为一个关键字的的集合。所有的关键字都取自与一个全序集　。
</code></pre><h2 id="动态集合上的操作"><a href="#动态集合上的操作" class="headerlink" title="动态集合上的操作"></a>动态集合上的操作</h2><pre><code>动态集合上的操作一般为两类操作：1. 查询操作　。2. 修改操作 。下面的为一些常见的操作

1. 给定一个集合 S 和关键字 k ，返回一个指向 S 中一个对象的指针 p ;　或者当　k 不存在时 , 返回 nil .
    SEARCH(S,k)

2. 将 x　指向的对象插入到集合 S 中去 . 
    INSERT(S,x)

3. 当给定一个指向 S 中的元素的指针 x 时 , 将 x 从 S 中删除 . 
    DELETE(S,x)

4. 获取指定集合 S 中的最小值 .
    MININUM(S)

5. 获取指定集合 S 中的最大值 .
    MAXNUM(S)

6.　获取指定集合 S 中比 x 大的下一个元素 . 
    SUCCESSOR(S, x)

7. 获取指定集合 S 中比 x 小的上一个元素 . 
    PREDECESSOR(S, x)
</code></pre><h2 id="栈及队列"><a href="#栈及队列" class="headerlink" title="栈及队列"></a>栈及队列</h2><pre><code>栈: 一种后进先出的数据结构 , 称为 LIFO ( last in, first out ) .　栈的删除只能删除最后插入的对象 ,  称之为入栈 ( POP ) . 栈的插入只能在最后插入的对象后面插入 , 称之为入栈 ( PUSH ) .
栈下溢: 对空栈进行删除操作.
栈上溢: 对满栈进行插入操作.

队列: 一种先进先出的数据结构 , 称为 FIFO (first in, first out ) . 队列的删除在队列头部，称为出队 (DEQUEUE) ,　队列的插入在队列尾部 , 称为入队 (EnQUEUE) .
队列下溢: 对空队列进行删除操作.
队列上溢: 对满队列进行插入操作.
</code></pre><h3 id="两个栈实现一个队列"><a href="#两个栈实现一个队列" class="headerlink" title="两个栈实现一个队列 ?"></a>两个栈实现一个队列 ?</h3><pre><code>我们将两个栈看成最后实现的队列,此时将实现看成黑盒子. 我们向队列中插入 1 到 7 ,　依次取数据为 1　到 7 .

此时我们有两个栈S1, s2, 

   S1 +-----+  top     S2 +----+   top 
      |     |             |    |
      |     |             |    |
      |     |             |    |
      |     |             |    |
      |     |             |    |
      |     |             |    |
      |     |             |    |
 bottom               bottom

 step 1: 将需要插入队列的对象插入 S1 , 我们假设为 1~7 , 下面标示为插入后的两个栈的数据分布情况.

   S1 +-----+  top     S2 +----+   top 
      |  1  |             |    |
      |  2  |             |    |
      |  3  |             |    |
      |  4  |             |    |
      |  5  |             |    |
      |  6  |             |    |
      |  7  |             |    |
 bottom               bottom

 step 2: 出栈时，先将 S1 中的数据安找入栈的顺序依次入栈 S2 . 并将 S2 栈底数据出栈.

   S1 +-----+  top     S2 +-----+   top 
      |     |             |  7  |
      |     |             |  6  |
      |     |             |  5  |
      |     |             |  4  |
      |     |             |  3  |
      |     |             |  2  |
      |     |             |  1  | ---- this node  will pop
 bottom               bottom

 Step 3: 完成数据弹出后, 按照 S2 的出栈的顺序入栈 S1 .

   S1 +-----+  top     S2 +-----+   top 
      |  2  |             |     |
      |  3  |             |     |
      |  4  |             |     |
      |  5  |             |     |
      |  6  |             |     |
      |  7  |             |     |
 bottom               bottom


step 2 中, S1 的最后一个元素不必插入到 S2 中 , 直接弹出即可 . 
step 3 中，完成队列的出栈后,　不必立即将 S2 数据弹出到 S1 . 如果对于本队列的下一次操作为弹出，直接在 S2 中操作即可 . 如果是插入操作，则将 S2 中数据按照 出栈顺序插入 S1 .
</code></pre><h3 id="两个队列实现栈"><a href="#两个队列实现栈" class="headerlink" title="两个队列实现栈 ?"></a>两个队列实现栈 ?</h3><pre><code>我们假设插入的数据为 1~7, 我们取出数据的顺序为 7 -&gt; 1.

假设我们有两个队列 q1, q2.

    q1                        q2
    end        head         end        head
    +-------------            +-------------
    |                       |              
    +-------------            +-------------

step 1: 将数据按照顺序插入到 q1 中 , 下面为数据在两个队列中的分布情况.

    q1                        q2
    end        head         end        head
    +-------------            +-------------
    |7 6 5 4 3 2 1          |              
    +-------------            +-------------

step 2: 除了在队末的数据，将在 q1 中的数据出列到 q2 中, 将 q1 中的数据出列,　完成数据的出栈.

    q1                        q2
    end        head         end        head
    +-------------            +-------------
    |7(DEQEUE)              |6 5 4 3 2 1    
    +-------------            +-------------

step 3: 将 q2 中的数据全部出列，并按照 q2 出列顺序入列 q1.

    q1                        q2
    end        head         end        head
    +-------------            +-------------
    |6 5 4 3 2 1           |               
    +-------------            +-------------
</code></pre><h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h2><pre><code>双向链表: 每一个元素都包含一个对象, 每个对象中包含一个关键字域(key)和两个指针域(next, prev), next[x] 指向链表中的 x 元素的后继元素, prev[x] 标示链表中 x 的前驱元素. 当 x　元素没有前驱元素时，此元素为head, 当元素没有后继元素时, 此元素为 tail. 
</code></pre><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">struct listnode</span><br><span class="line">&#123;</span><br><span class="line">    struct listnode *prev;</span><br><span class="line">    struct listnode *next;</span><br><span class="line">    dataType key.</span><br><span class="line">    .... // other data</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="链表的基本操作"><a href="#链表的基本操作" class="headerlink" title="链表的基本操作"></a>链表的基本操作</h3><ul>
<li><p>链表的搜索</p>
<p>  LIST-SEARCH(L, k)</p>
<pre><code>x ← head[L]
while x != nil and key[x] != k
    do x ← next[x]
return x
</code></pre></li>
<li><p>链表的插入<br>  LIST-INSERT(L,new)</p>
<pre><code>x ← head[L]
while x != nil
    x ← next[x]
next[x] ← new
prev[nex] ← x
</code></pre></li>
<li><p>链表的删除<br> List-DELETE(L,k)</p>
<pre><code>x ← head[L]
while x != nil and key[x] != k
    x ← next[x]
if x == nil
    return nil
delNode ← x
prev[delNode] ← next[delNode]
prev[next[delNode]] ← prev[delNode]
</code></pre><p> 有的语言并不支持指针，我们在不支持指针的语言中实现链表，用数组下标来代替 prev 和 next 这两个指针.</p>
</li>
</ul>
<h2 id="code-1"><a href="#code-1" class="headerlink" title="[code][1]"></a>[code][1]</h2><p>1:  <a href="mailto:git@github.com" target="_blank" rel="noopener">git@github.com</a>:singledo/SortCode.git</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://octopuscloud.top/2019/04/21/十章－数据结构/" data-id="ck471vq1r002732fzd6fk8vb0" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/data-struct/">data struct</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/04/28/十一章-散列表/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          第十一章-散列表
        
      </div>
    </a>
  
  
    <a href="/2019/04/14/八章-排序/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">算法导论-第八章</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/RFC/">RFC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/RFC-protocol/">RFC protocol</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ReadNote/">ReadNote</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/protocols/">protocols</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/tools/">tools</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Struct/">Data Struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ethernet-II/">Ethernet II</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Frame-Format/">Frame Format</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/I2C/">I2C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/IPv6/">IPv6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Neighbour-Discover-Protocol/">Neighbour Discover Protocol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RFC/">RFC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SNMP/">SNMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/arthmetic/">arthmetic</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cgdb/">cgdb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/chapter-15/">chapter 15</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-struct/">data struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/deb/">deb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/defalt-path-for-so-file/">defalt path for so file</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/editer/">editer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/file-system/">file system</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/gdb-debug/">gdb debug</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux-driver/">linux driver</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/platform-bus/">platform bus</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pointer-array/">pointer, array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pseudocode/">pseudocode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rb-tree/">rb tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sort/">sort</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ssh-key/">ssh key</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/symbol/">symbol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tool/">tool</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tools/">tools</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/图/">图</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/通信协议/">通信协议</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/C/" style="font-size: 10px;">C</a> <a href="/tags/Data-Struct/" style="font-size: 10px;">Data Struct</a> <a href="/tags/Ethernet-II/" style="font-size: 10px;">Ethernet II</a> <a href="/tags/Frame-Format/" style="font-size: 10px;">Frame Format</a> <a href="/tags/I2C/" style="font-size: 10px;">I2C</a> <a href="/tags/IPv6/" style="font-size: 15px;">IPv6</a> <a href="/tags/Neighbour-Discover-Protocol/" style="font-size: 10px;">Neighbour Discover Protocol</a> <a href="/tags/RFC/" style="font-size: 10px;">RFC</a> <a href="/tags/SNMP/" style="font-size: 10px;">SNMP</a> <a href="/tags/arthmetic/" style="font-size: 10px;">arthmetic</a> <a href="/tags/cgdb/" style="font-size: 10px;">cgdb</a> <a href="/tags/chapter-15/" style="font-size: 10px;">chapter 15</a> <a href="/tags/data-struct/" style="font-size: 15px;">data struct</a> <a href="/tags/deb/" style="font-size: 10px;">deb</a> <a href="/tags/defalt-path-for-so-file/" style="font-size: 10px;">defalt path for so file</a> <a href="/tags/editer/" style="font-size: 10px;">editer</a> <a href="/tags/file-system/" style="font-size: 10px;">file system</a> <a href="/tags/gdb-debug/" style="font-size: 10px;">gdb debug</a> <a href="/tags/hash/" style="font-size: 10px;">hash</a> <a href="/tags/linux/" style="font-size: 20px;">linux</a> <a href="/tags/linux-driver/" style="font-size: 10px;">linux driver</a> <a href="/tags/platform-bus/" style="font-size: 10px;">platform bus</a> <a href="/tags/pointer-array/" style="font-size: 10px;">pointer, array</a> <a href="/tags/pseudocode/" style="font-size: 10px;">pseudocode</a> <a href="/tags/rb-tree/" style="font-size: 10px;">rb tree</a> <a href="/tags/sort/" style="font-size: 20px;">sort</a> <a href="/tags/ssh-key/" style="font-size: 10px;">ssh key</a> <a href="/tags/symbol/" style="font-size: 10px;">symbol</a> <a href="/tags/tool/" style="font-size: 10px;">tool</a> <a href="/tags/tools/" style="font-size: 10px;">tools</a> <a href="/tags/图/" style="font-size: 10px;">图</a> <a href="/tags/通信协议/" style="font-size: 10px;">通信协议</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">December 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/11/">November 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/12/15/TMUX-使用/">TMUX-使用</a>
          </li>
        
          <li>
            <a href="/2019/11/02/linux-platform-bus-总线分析/platform/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/11/02/十二章-二叉搜索树/">算法导论-第十二章 二叉查找树</a>
          </li>
        
          <li>
            <a href="/2019/11/02/SegmentationFault-Debug/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/10/19/linux-platform-bus-总线分析/">linux platform bus 总线分析</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 zhangjun<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>